/**
 * 96. 不同的二叉搜索树
 * https://leetcode-cn.com/problems/unique-binary-search-trees/
 */

/**
 * @param {number} n
 * @return {number}
 */
function numTrees(n) {
  const stack = new Array(n + 1).fill(1);
  for (let i = 2; i <= n; i += 1) {
    let count = 0;
    for (let j = 1; j <= i; j += 1) {
      count += stack[j - 1] * stack[i - j];
    }
    stack[i] = count;
  }
  return stack[n];
}

console.log(numTrees(3) === 5);
console.log(numTrees(1) === 1);
